/*
 * @Author: 缄默
 * @Date: 2021-09-28 12:16:37
 * @LastEditors: 缄默
 * @LastEditTime: 2022-04-13 15:54:32
 */

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;


//链表结构体的定义
struct ListNode {
    int value;
    ListNode* next;
    //链表的构造函数
    ListNode(int x) : value(x), next(nullptr) { }
    ListNode() : value(0), next(nullptr) { }
};

//判断字符串是否是回文串
//时间复杂度O(n) 空间复杂度O(1)
bool isPalindrome(ListNode* const head) {

    //双指针寻找中间节点
    ListNode* fastIter = head;
    ListNode* slowIter = head;
    while (fastIter->next != nullptr && fastIter->next->next != nullptr) {
        fastIter = fastIter->next->next;
        slowIter = slowIter->next;
    }
    ListNode* cur = head;
    //反转中间节点
    ListNode* lastNode = reverseList(slowIter->next);
    ListNode* rightNode = lastNode;
    while (rightNode != nullptr && cur!= nullptr && rightNode->value == cur->value) {
        rightNode = rightNode->next;
        cur = cur->next;
    }
    lastNode = reverseList(lastNode);
    slowIter->next = lastNode;
    printList(head);
    return !(rightNode != nullptr && cur!= nullptr);


}

//反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* cur = head;//当前操作节点    
    ListNode* pre = nullptr;//当前操作节点的前一个节点 
    ListNode* next = nullptr;//当前操作节点的下一个节点
    while (cur != nullptr) {
        next = cur->next;//记录下当前操作节点的下一个节点
        cur->next = pre;//将当前操作节点指向上一个节点
        pre = cur;//将当前操作节点记录到pre
        cur = next;//将下一个操作节点转化为操作节点
    }
    return pre;
}

//打印链表
void printList(ListNode* const head) {
    ListNode* cur = head;
    while (cur != nullptr) {
        cout << cur->value << " ";
        cur = cur->next;
    }
    cout << endl;
}

//通过数组生成链表
ListNode* foundList(vector<int>& arr, ListNode* head) {
    ListNode* cur = head;
    auto iter = arr.begin();
    cur->value = *iter;
    iter++;
    while (iter < arr.end()) {
        cur->next = new ListNode(*iter);
        cur = cur->next;
        iter++;
    }
    return head;
}

//删除倒数第k个节点
ListNode* removeLastKNode(ListNode* const head, int K) {
    if (K <= 0 ) {
        return head;
    }
    ListNode* cur = head;
    ListNode* removeNode = head;
    for (int i = 0; i < K; i++) {
        cur = cur->next;
    }
    while (cur->next != nullptr) {
        removeNode = removeNode->next;
        cur = cur->next;
    }
    removeNode->next = removeNode->next->next;
    return head;
}